package offerbook;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
 * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，找target是否在数组中。
 * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
 * @date 2020/3/7 23:39
 */
public class Code08_FindTargetInRotateArr {
    /**
     * 1：数组严格递增。正常按照二分查找去搜索
     * 若arr[mid] >= arr[left]，那么判断target在这之间还是在mid右侧
     * 若arr[mid] < arr[right]，那么判断target在这之间还是在mid左侧
     */
    public static boolean targetNumberInRotateArray1(int [] arr, int target) {
        if(arr == null || arr.length == 0) return false;
        int left = 0;
        int right = arr.length -1;
        int mid = (left + right)/2;
        //一直搜索，搜索一次判断target位于哪一侧
        while (left <= right){
            if(arr[mid] == target) return true;
            //如果搜索来到左侧大的区域
            if(arr[left] <=  arr[mid]){
                //若target位于二者之间，顺序搜索
                if(arr[left] <= target && target <= arr[mid]){
                    right = mid -1;
                }else {//target位于mid+1后面
                    left = mid + 1;
                }
            //否则搜索来到右侧小的区域 ，arr[left] >  arr[mid]
            }else{
                //若target位于二者之间，顺序搜索
                if(arr[mid] <= target && target <= arr[right]){
                    left = mid +1;
                }else {//target位于mid-1后面
                    right = mid -1;
                }
            }
            mid = (left + right)/2;
        }
        return false;
    }

    /**
     * 第2类：数组非严格递增
     * 10111 和 11101 这种。
     * 此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，
     * 此时 start++ 即可。相当于去掉一个重复的干扰项。
     */

    public static boolean targetNumberInRotateArray2(int [] arr, int target) {
        if(arr == null || arr.length == 0) return false;
        int left = 0;
        int right = arr.length -1;
        int mid = (left + right)/2;
        //一直搜索，搜索一次判断target位于哪一侧
        while (left <= right){
            if(arr[mid] == target) return true;
            //分不清10111 和 11101 哪种情况，去除一个重复值 ，因为该重复值肯定不是target
            if(arr[left] == arr[mid]) {
                left ++;
                mid = (left + right) >> 1;
                continue;
            }
            //如果搜索来到左侧大的区域
            if(arr[left] <=  arr[mid]){
                //若target位于二者之间，顺序搜索
                if(arr[left] <= target && target <= arr[mid]){
                    right = mid -1;
                }else {//target位于mid+1后面
                    left = mid + 1;
                }
                //否则搜索来到右侧小的区域 ，arr[left] >  arr[mid]
            }else{
                //若target位于二者之间，顺序搜索
                if(arr[mid] <= target && target <= arr[right]){
                    left = mid +1;
                }else {//target位于mid-1后面
                    right = mid -1;
                }
            }
            mid = (left + right)/2;
        }
        return false;
    }

    public static void main(String[] args) {
//        int[]arr = {3,4,5,6,7,8,9,10,-11,-10,-9,-8,-7,-6};
        int[]arr = {3,1};
     /*   for (int i : arr) {
            if(!targetNumberInRotateArray1(arr,i)){
                System.out.println("error");
                System.out.println(i);
            }
        }*/
        System.out.println(targetNumberInRotateArray2(arr, 1));


    }
}
